/*
day304 
2020.6.27 
*/
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;

class Solution {
public:
    int majorityElement(vector<int>& nums) {
		unordered_map<int,int> m;
		int max=0,res=nums.front();
		for(int i=0;i<nums.size();i++)
		{
			int tem=++m[nums[i]];
			if(tem>max)
			{
				max=tem;
				res=nums[i];
			}
		} 
		
		if(max>nums.size()/2)
		{
			return res;
		}
		
		return -1;
    }
};


class Solution1 {
public:
    int majorityElement(vector<int>& nums) {
        int size = nums.size();
        int cnt = 0, major;
        for(int n : nums){
            if(cnt == 0){
                major = n;
                cnt ++;
            }
            else{
                if(major == n) cnt ++;
                else cnt --;
            }
        }
        int C = 0;
        for(int i = 0; i < size; i++) {
            if(nums[i] == major) C++;
        }
        if(C <= size / 2) major = -1;
        return major;
    }
};
int main()
{
	return 0;
}
